package cn.arnold.treeapplication.avl;

public class AVTDemo {
    public static void main(String[] args) {
        //int[] arr = {4,3,6,5,7,8};
        //int[] arr = { 10, 12, 8, 9, 7, 6 };
        int[] arr = { 10, 11, 7, 6, 8, 9 };
        AVT avt = new AVT();
        // 添加节点
        for (int i = 0; i <arr.length ; i++) {
            avt.add(new Node(arr[i]));
        }
        System.out.println("树的高度="+avt.getRoot().getHeight());
        System.out.println("树的左子树高度="+avt.getRoot().leftHeight());
        System.out.println("树的右子树的高度="+avt.getRoot().rightHeight());
        System.out.println("根节点的左子节点="+avt.getRoot());
    }


}


class AVT {
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    // 添加
    public void add(Node node) {
        if (root == null) {
            root = node;
        }else {
            root.add(node);
        }

    }
}


class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int vlaue) {
        this.value = vlaue;
    }

    @Override
    public String toString() {
        return "Node{" +
                "vlaue=" + value +
                '}';
    }

    // 获取以当前节点为根节点的树的高度（左树高度和右树高度取较大值）
    public int getHeight() {
        return Math.max((left == null ? 0 : left.getHeight()), (right == null ? 0 : right.getHeight()))+1;

    }

    // 获取左子树高度
    public int leftHeight() {
        return left == null ? 0 : left.getHeight();
    }

    // 获取右子树高度
    public int rightHeight() {
        return right == null ? 0 : right.getHeight();
    }

    // 左旋转(6句代码)
    public void leftRotate() {
        Node tempNode = new Node(this.value);
        tempNode.left = this.left;
        tempNode.right = this.right.left;
        this.value = this.right.value;
        this.right = this.right.right;
        this.left = tempNode;
    }

    // 右旋转(6句代码)
    public void rightRotate() {
        Node tempNode = new Node(this.value);
        tempNode.right = this.right;
        tempNode.left = this.left.right;
        this.value = this.left.value;
        this.left = this.left.left;
        this.right = tempNode;
    }

    // 添加节点创建平衡二叉树
    public void add(Node node) {
        // 先满足排序二叉树规则
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }
        if (node.value > this.value) {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        // 满足平衡二叉树规则
        // 左旋转
        if ((rightHeight()-leftHeight()) > 1) {
            // 判断是否需要进行右旋转
            // 如果它右子树的左子树的高度大于它右子树右子树的高度，则先进行右旋转
            if (right != null && right.leftHeight() > right.rightHeight()) {
                right.rightRotate();
                leftRotate();
            } else {
                leftRotate();
            }
            return;     //!!!!
        }

        // 右旋转
        if ((leftHeight()-rightHeight()) > 1) {
            // 判断是否需要进行右旋转
            // 如果它左子树的右子树的高度大于它左子树左子树的高度，则先进行左旋转
            if (left != null && left.leftHeight() < left.rightHeight()) {
                left.leftRotate();
                rightRotate();
            } else {
                rightRotate();
            }
        }
    }
}